\setcounter{chapter}{0}
\setcounter{section}{0}
\chapter{Tính toán song song}     % Enter chapter title between curly braces

\section{Giới thiệu chung}  % Enter section title between curly braces

\subsection{Nhu cầu về tốc độ tính toán}    % Enter subsection title between curly braces
Ngày nay, với các bài toán yêu cầu xử lý trên một số lượng dữ liệu lớn và phức tạp như sự mô phỏng những hệ thống phức tạp và "những vấn đề thách thức lớn" như: dự báo thời tiết và khí hậu, những phản ứng hóa học và hạt nhân, hệ gen sinh học,...đặt ra một nhu cầu lớn về tốc độ tính toán. Những bài toán này thường yêu cầu một lượng lớn các phép tính lặp lại trên một khối lượng lớn dữ liệu để đưa ra một kết quả đúng đắn, và các phép tính này cần hoàn thành trong một khoảng thời gian hợp lý. Ví dụ như bài toán dự báo thời tiết không thể xử lý được bằng các máy tính thông thường vì thời gian xử lý là khoảng 10 năm, điều này hoàn toàn không phù hợp.\\
\indent	Để giải quyết được các bài toán trên ta cần phải tăng tốc độ tính toán.\\
	Mặc dù trong những thập kỉ vừa qua chúng ta đã được chứng kiến những thành tựu to lớn về công nghệ vi xử lý. Tốc độ đồng hồ của các bộ xử lý đã tăng từ khoảng 40MHz (MIPS R3000, circa 1988) tới trên 2,0 GHz (Pentium 4, circa 2002); cùng một lúc, các bộ xử lý có khả năng thực hiện đa chỉ lệnh trong cùng một chu kỳ...Nhưng do giới hạn về vật lý nên khả năng tính toán của các bộ xử lý không thể tăng mãi được.\\
\indent Một cách để tăng tốc độ tính toán đó là sử dụng tính toán song song.
\subsection{Khái niệm chung}
Thông thường, phần mềm được viết trên máy tính tuần tự có đặc điểm:
\begin{itemize}
\item Được chạy trên một máy tính đơn với một bộ xử lý(CPU).
\item Một bài toán được thực hiện bằng một chuỗi các dòng lệnh rời rạc, các dòng lệnh này được thực hiện nối tiếp nhau.
\item Tại mỗi thời điểm chỉ có một dòng lệnh được thực hiện.
\end{itemize}
\begin{figure}[!ht]
\centering
\includegraphics[scale=0.75]{tttuantu}
\caption{\textit{Mô hình tính toán tuần tự}}\label{fig:Hình}
\end{figure}
\indent Theo nghĩa đơn giản nhất, tính toán song song là sử dụng đồng thời nhiều tài nguyên tính toán để giải quyết một bài toán tính toán. Có đặc điểm sau:
\begin{itemize}
\item Được thực hiện trên nhiều bộ xử lý.
\item Một bài toán được chia thành các phần rời rạc, các phần này có thể được giải quyết đồng thời.
\item Từng phần nhỏ được giải quyết theo mô hình tuần tự.
\item Các dòng lệnh của mỗi phần thực thi một cách đồng thời trên các bộ xử lý khác nhau.
\end{itemize}
Các tài nguyên tính toán ở đây có thể là: một máy tính đơn với nhiều bộ xử lý, một số lượng máy tính tùy ý được nối với nhau bằng đường mạng hoặc có thể là sự kết hợp của hai mô hình trên.
\begin{figure}[!ht]
\centering
\includegraphics[scale=0.55]{mohinhttss}
\caption{\textit{Mô hình tính toán song song}}\label{fig:Hình}
\end{figure}
\subsection{Phạm vi của tính toán song song}
Tính toán song song đã làm nên những tác động to lớn trong nhiều lĩnh vực đang còn hạn chế từ việc mô phỏng tính toán cho các ứng dụng kĩ thuật và khoa học cho tới các ứng dụng thương mại trong vấn đề khai mỏ dữ liệu và xử lý giao dịch. Dưới đây là một số các ứng dụng đa dạng của tính toán song song.
\subsubsection{Các ứng dụng trong kĩ thuật và thiết kế}
Tính toán song song đã được sử dụng và đã mang lại những thành công lớn trong việc thiết kế cánh máy bay (tối ưu hóa sự nâng, sự kéo và tính bền vững), động cơ đốt trong (tối ưu hóa sự phân phối điện và sự cháy), các mạch tốc độ cao và các cấu trúc khác.\\
\indent Các ứng dụng khác trong thiết kế và kĩ thuật tập trung vào sự tối ưu hóa nhiều quá trình. Các máy tính đã được dùng để giải nhiều bài toán tối ưu hóa liên tục và rời rạc. Các thuật toán đơn hình, phương pháp điểm trong việc tối ưu đường thẳng, phân nhánh và giới hạn (Branch and bound), lập trình di truyền cho tối ưu rời rạc đã được song song hóa một cách hiệu quả và được sử dụng thường xuyên.
\subsubsection{Các ứng dụng trong khoa học}
Trong những năm qua chúng ta đã được chứng kiến cuộc cách mạng trong việc ứng dụng tính toán khoa học hiệu năng cao. Việc sắp xếp có thứ tự bộ gen người đã mở ra những biên giới mới thú vị trong nghành tin sinh học. Sự đặc trưng cấu trúc, chức năng của gen và protein nắm giữ sự hứa hẹn về kiến thức và uy thế căn bản của các quá trình sinh học. Việc phân tích các chuỗi sinh học theo hướng phát triển những loại thuốc và cách điều trị mới đối với bệnh tật và các điều kiện y học yêu cầu những thuật toán có tính đổi mới là một lĩnh vực yêu cầu khả năng tính toán quy mô lớn. Hơn thế nữa, những kỹ thuật tính toán song song mới nhất được mục tiêu hóa đặc biệt theo hướng ứng dụng trong tin sinh học.\\
\indent Những thành tựu trong hóa học và vật lý học tính toán tập trung vào các nghiên cứu được xếp theo quy mô từ các hiện tượng lượng tử cho tới các cấu trúc phân tử lớn. Những nghiên cứu này đã cho kết quả trong việc thiết kế nguyên liệu mới và những quy trình hiệu quả hơn. Các ứng dụng trong vật lý học thiên thể đã được khám phá đó là sự nở giãn của thiên hà, các quy trình nhiệt hạch, và phân tích kho dữ liệu khổng lồ từ các kính thiên văn. Việc mô phỏng thời tiết, khai thác khoáng sản, dự báo lũ lụt,.v.v dựa chủ yếu vào máy tính song song và có tác động quan trọng tới cuộc sống hàng ngày.
\subsubsection{Các ứng dụng trong thương mại}
Với hiệu ích lan rộng của web được tích hợp các nôi dung động và tĩnh đang gia tăng nhấn mạnh tời nhu cầu về các máy chủ chi phí thấp có khả năng cung cấp thể hiện có thể biến đổi được. Các mô hình song song từ đa bộ xử lý tới máy cụm linux được sử dụng như là các máy chủ cơ sở dữ liệu và web.\\
\indent Tính sẵn sàng của dữ liệu giao dịch quy mô lớn đóng vai trò đáng kể trong việc khai mỏ dữ liệu, phân tích tối ưu hóa công việc kinh doanh và các quyết định marketing. Khối lượng lớn và sự phân bố theo địa lý của những dữ liệu đòi hỏi sử dụng các thuật toán song song hiệu quả đối với những bài toán như khai mỏ quy tắc kết hợp, phân nhóm, phân lớp và phân tích chuỗi thời gian.\\
\subsubsection{Các ứng dụng trong hệ thống máy tính}
Khi các hệ thống máy tính trở nên rộng khắp và sự tính toán trải rộng trên toàn mạng, thì các vấn đề xử lý song song cũng được ứng dụng nhiều hơn. Trong việc bảo mật máy tính, việc phát hiện xâm phạm là một thử thách đáng kể. Trong trường hợp phát hiện xâm phạm mạng, dữ liệu được thu thập từ các trang phân tán và phải được phân tích một cách nhanh chóng. Việc không thể thu thập được dữ liệu này tại một vị trí trung tâm để phân tích đòi hỏi các thuật giải song song và phân tán. Trong lĩnh vực mật mã, ứng dụng đặc biệt nhất của tính toán song song trên Internet tập trung vào việc phân tích các số nguyên cực lớn.\\
\indent Các hệ thống nhúng tăng dựa trên các thuật toán điều khiển phân tán để hoàn thành một số tác vụ. Một ô tô hiện đại gồm mười bộ xử lý liên lạc với nhau để thực hiện các tác vụ phức tạp trong việc tối ưu hóa quá trình tiến hành và sự thực hiện. Trong các hệ thống này, các thuật toán phân tán và song song truyền thống để lựa chọn vật dẫn đầu và tập độc lập lớn nhât, vv...thường được sử dụng.

\section{Các loại máy tính song song}
\subsection{Phân loại máy tính của Flynn}
\indent Dù là máy tính tuần tự hay song song đều phải thực hiện bằng cách thực thi các chỉ lệnh trên dữ liệu.\\
\indent Dòng chỉ lệnh nói cho máy tính biết phải làm gì.\\
\indent Dòng dữ liệu bị ảnh hưởng bởi các chỉ lệnh.\\
\indent Dựa vào số lượng dòng lệnh và số lượng dòng dữ liệu thực hiện tại cùng một thời điểm Micheal Flynn đã phân các máy tính thành 4 loại.
\begin{itemize}
\item Máy tính SISD: đơn dòng lệnh-đơn dòng dữ liệu (Single Instruction Stream-Single Data Stream)
\subitem Máy tính SISD chỉ có một bộ xử lý, ở mỗi thời điểm thực hiện một chỉ lệnh và chỉ đọc, ghi một mục dữ liệu. Máy tính SISD còn được gọi là đơn chương trình-đơn dòng dữ liệu, SPSD (Single Program Stream-Single Data Stream). Vì chỉ có một bộ xử lý nên các thuật toán cho máy tính SISD không bao hàm tính song song.
\begin{figure}[!ht]
\centering
\includegraphics[scale=0.55]{SISD}
\caption{\textit{Mô hình máy tính SISD}}\label{fig:1.1}
\end{figure}

\item Máy tính MISD: đa dòng lệnh - đơn dòng dữ liệu (Multiple Instruction Stream - Single Data Stream)\\
\begin{figure}[ht]
\centering
\includegraphics[scale=0.6]{MISD}
\caption{\textit{Mô hình máy tính MISD}}\label{fig:1.2}
\end{figure}
Máy tính MISD có nhiều bộ xử lý, mỗi bộ xử lý có đơn vị điều khiển (Control Unit) riêng, chia sẻ một bộ nhớ chung. Máy tính MISD còn được gọi là MPSD (Multiple Program Stream - Single Data Stream, đa chương trình - đơn dòng dữ liệu).\\
 Tính song song có thể đạt được trong hệ thống máy MISD bằng cách  cho các bộ xử lý thực hiện các công việc khác nhau tại cùng một thời điểm trên cùng một tập dữ liệu.
\item Máy tính SIMD: đơn dòng lệnh-đa dòng dữ liệu (Single Instruction stream-Multiple Data Stream)\\
\begin{figure}[ht]
\centering
\includegraphics[scale=0.6]{SIMD}
\caption{\textit{Mô hình máy tính SIMD}}\label{fig:1.3}
\end{figure}
Máy tính SIMD có một đơn vị điều khiển để điều khiển nhiều bộ xử lý thực hiện theo một dòng lệnh đơn. Tức là các bộ xử lý này thực hiện cùng một câu lệnh trên các mục dữ liệu khác nhau. Máy tính SIMD còn được gọi là máy tính SPMD, đơn chương trình - đa dòng dữ liệu.\\
Các bài toán giải quyết được SIMD yêu cầu các bộ xử lý giao tiếp với nhau để trao đổi dữ liệu hay kết quả. Việc này có thể được thực hiện theo hai cách: \begin{itemize}
\item Sử dụng bộ nhớ chia sẻ và các biến chia sẻ.
\item Sử dụng một số dạng liên kết mạng và truyền thông điệp(bộ nhớ phân tán).
\end{itemize}

\item Máy tính MIMD: đa dòng lệnh - đa dòng dữ liệu (Multiple Instruction Stream-Multiple Data Stream)\\
\begin{figure}[!ht]
\centering
\includegraphics[scale=0.6]{MIMD}
\caption{\textit{Mô hình máy tính MIMD}}\label{fig:1.4}
\end{figure}
Máy tính MIMD có $N$ bộ xử lý, $N$ dòng lệnh, và $N$ dòng dữ liệu. Mỗi bộ xử lý có thể thực hiện chỉ lệnh từ đơn vị điều khiển riêng của nó. Tức là các bộ xử lý có thể làm các việc khác nhau trên các dữ liệu khác nhau tại cùng một thời điểm.\\
\indent Đây là loại máy tổng quan và mạnh nhất trong các loại máy song song. Hai loại máy tính song song cơ bản nhất là hệ thống đa bộ xử lý bộ nhớ chia sẻ và hệ thống đa máy tính bộ nhớ phân tán đều thuộc loại máy MIMD.\\
\indent Máy tính MIMD với bộ nhớ chia sẻ được gọi là multiprocessors (máy đa bộ xử lý). Ví dụ các máy ENCORE, MULTIMAX, SEQUENT và BALANCE.\\
\indent Máy tính MIMD với một mạng liên kết được gọi là multicomputers (hệ đa máy tính), đôi khi được gọi là hệ thống phân tán. Ví dụ INTEL iPSC, NCUBE/7 và các mạng transputer.\\
\end{itemize}
Ta có thể tổng quát khả năng của 4 loại máy tính theo nguyên tắc Flynn như sau:
\begin{figure}[h]
\centering
\includegraphics[scale=0.75]{tongquan}
\caption{\textit{Chức năng của 4 mô hình máy tính}}\label{fig:1.4}
\end{figure}

\subsection{Kiến trúc bộ nhớ của máy tính song song}
\subsubsection{Hệ thống đa bộ xử lý bộ nhớ chia sẻ}
\begin{itemize}
\item Đặc điểm chung:
\begin{itemize}
\item Một máy tính thông thường chứa một bộ xử lý để thực thi chương trình được lưu trong bộ nhớ chính. Mỗi vùng trong bộ nhớ chính được xác định bằng các số gọi là địa chỉ của nó. Địa chỉ được đánh số bắt đầu từ $0$ cho tới $2^{n}-1$ nếu có $n$ bit trong địa chỉ.
\item Mô hình bộ nhớ chia sẻ được mở rộng từ mô hình bộ xử lý đơn. Mô hình bộ nhớ chia sẻ có đa bộ xử lý được kết nối tới các module của bộ nhớ đa. các bộ xử lý kết nối tới bộ nhớ có thể qua một số dạng mạng liên kết.
\item Hệ thống đa bộ xử lý bộ nhớ chia sẻ làm việc với một không gian địa chỉ đơn, tức là mỗi vùng trong toàn bộ hệ thống bộ nhớ chính có một địa chỉ duy nhất, tất cả các bộ xử lý truy cập tới vùng nhớ đó theo địa chỉ này.
\item Máy tính chia sẻ bộ nhớ được chia thành 2 loại dựa trên thời gian truy cập bộ nhớ, đó là : truy cập bộ nhớ đồng dạng (Uniform Memory Access, UMA) và truy cập bộ nhớ không đồng dạng (Nonuniform Memory Access, NUMA).\begin{itemize}
\item Truy cập bộ nhớ đồng dạng: Thời gian và mức độ truy cập tới bộ nhớ là như nhau đối với mỗi bộ xử lý. Khi kiến trúc bộ nhớ có gắn thêm bộ đệm nhất quán thì sự truy cập của một bộ xử lý tới bộ nhớ chia sẻ là rõ ràng đối với các bộ xử lý còn lại, được gọi là bộ đệm gắn kết nhất quán truy cập đồng dạng(Cache coherent UMA, CC-UMA).
\item Truy cập bộ nhớ không đồng dạng: Bộ nhớ chia sẻ được phân tán cho các bộ xử lý thành bộ nhớ cục bộ và tuyển tập tất cả các đơn thể bộ nhớ tạo ra bộ nhớ chung cho các bộ xử lý. Thời gian truy cập tới bộ nhớ cục bộ nhanh hơn thời gian truy cập tới bộ nhớ không cục bộ. Khi được gắn thêm bộ đêm nhất quán ta có khái niệm bộ đệm nhất quán truy cập không đồng dạng (CC-NUMA)
\end{itemize}
\end{itemize}
\item Ưu điểm
\begin{itemize}
\item Không gian địa chỉ chung được cung cấp cho người sử dụng một cách thân thiện bởi một chương trình tương thích với bộ nhớ.
\item Sự phân chia dữ liệu giữa các tác vụ nhanh và đồng dạng do bộ nhớ gần với các bộ xử lý.
\end{itemize}
\item Nhược điểm
\begin{itemize}
\item Khó thể hiện phần cứng để tất cả các bộ xử lý đạt được tốc độ truy cập nhanh tới tất cả bộ nhớ chia sẻ.
\item Vì các bộ xử lý được kết nối với bộ nhớ nên khi muốn tăng thêm bộ xử lý sẽ gặp nhiều khó khăn về thiết kế và sản xuất vì sẽ làm tăng các giao tiếp trên bộ nhớ chung, đối với hệ thống bộ đệm nhất quán, giao tiếp tăng sẽ đặt ra đòi hỏi quản lý bộ nhớ/bộ đệm.
\end{itemize}
\end{itemize}
\begin{figure}[!ht]
\begin{minipage}[b]{0.4\textwidth}
\centering
\includegraphics[scale=0.30]{sharedmemory}
\caption{\textit{Máy tính bộ nhớ chia sẻ}}\label{fig:*1}
\end{minipage}
\hfill
\begin{minipage}[b]{0.4\textwidth}
\centering
\includegraphics[scale=0.35]{distributedmemory}
\caption{\textit{Máy tính bộ nhớ phân tán}}\label{fig:*2}
\end{minipage}
\end{figure}
\subsubsection{Hệ thống đa máy tính bộ nhớ phân tán}
\begin{itemize}
\item Đặc điểm chung
\subitem Hệ thống được tạo thành bằng cách kết nối các máy tính hoàn chỉnh qua một mạng liên kết. Mỗi máy tính có một bộ xử lý và bộ nhớ cục bộ không thể bị truy cập từ các bộ xử lý khác trong hệ thống.
\subitem Bộ nhớ được phân tán giữa các máy tính và mỗi bộ nhớ có không gian địa chỉ riêng. Mỗi bộ xử lý chỉ có thể truy cập vào vùng bộ nhớ riêng của nó. 
\subitem Một bộ xử lý muốn truy cập vào vùng dữ liệu của một máy tính cần gửi thông điệp (message)qua mạng liên kết. Thông điệp này có thể là dữ liệu mà các bộ xử lý khác yêu cầu cho tính toán của chúng.
\item Ưu điểm
\subitem Kiến trúc vật lý của hệ thống phân tán bộ nhớ đơn giản hơn hệ thống bộ nhớ chia sẻ nên dễ dàng để làm lớn hệ thống.
\subitem Mỗi bộ xử lý có thể nhanh chóng truy cập vào bộ nhớ riêng của mình mà không có giao thoa hay cố gắng duy trì sức kết dính bộ đệm.
\subitem Do có thể sử dụng các bộ xử lý và các mạng thông thường nên chi phí không quá cao.
\item Nhược điểm
\subitem Đòi hỏi người lập trình phải xác lập một số lượng lớn các giao tiếp dữ liệu giữa các bộ xử lý.
\subitem Dữ liệu không được chia sẻ, nên phải được sao lại. Đây có thể là khó khăn trong các ứng dụng yêu cầu nhiều thao tác trên một lượng lớn dữ liệu.
\subitem Thời gian truy cập bộ nhớ không đồng dạng (NUMA)
\end{itemize}
\subsubsection{Hệ thống bộ nhớ chia sẻ-phân tán}
\begin{figure}[!ht]
\centering
\includegraphics[scale=0.75]{hybidmemory}
\caption{\textit{Máy tính bộ nhớ chia sẻ-phân tán}}\label{fig:Hình}
\end{figure}
\begin{itemize}
\item Đặc điểm chung
\begin{itemize}
\item Hệ thống được kết hợp từ hai mô hình trên. Trong mô hình này mỗi bộ xử lý có thể truy cập tới toàn bộ bộ nhớ sử dụng một không gian địa chỉ đơn. 
\item Khi một bộ xử lý truy cập tới một vùng nhớ không phải là vùng nhớ cục bộ của mình, thì việc truyền thông điệp diễn ra để chuyển dữ liệu từ bộ xử lý đó tới vùng nhớ hoặc từ vùng nhớ tới bộ xử lý bằng một số phương thức được tự động điều này đã dấu đi sự thật là bộ nhớ được phân tán.
\item Đối với một hệ thống bộ nhớ được phân tán một cách vật lý, người ta sử dụng bộ nhớ \textit{cache} cục bộ tới mỗi bộ xử lý để có được bộ nhớ chia sẻ giữa các bộ xử lý. Khi cần giao tiếp, dữ liệu được copy từ các bộ nhớ \textit{cache}.
\item Những máy tính nhanh nhất và lớn nhất sử dụng kiến trúc bộ nhớ chia sẻ-phân tán. Xu hướng phát triển hiện nay dự báo rằng kiến trúc bộ nhớ này sẽ tiếp tục lân áp và tăng nhanh về cả số lượng và phạm vi sử dụng.
\end{itemize}
\item Ưu điểm và nhược điểm: là bất kì điểm chung nào cuả hai loại kiến trúc bộ nhớ trên.
\end{itemize}
\section{Các mô hình lập trình song song}
Ở trên chúng ta đã xem xét các thể hiện phần cứng cho tính toán song song, các mô hình máy tính song song. Vấn đề quan trọng đặt ra là phải viết một chương trình bằng một ngôn ngữ lập trình bậc cao và chạy trên một môi trường xác định sao cho tận dụng hết được khả năng của máy tính.\\
\indent Mô hình lập trình song song là sự trừu tượng hóa trên các kiến trúc phần cứng và bộ nhớ của máy tính song song. Mô hình lập trình song song không đặc tả riêng cho một loại kiến trúc bộ nhớ hay máy tính cụ thể. Một cách lý thuyết thì môt loại mô hình lập trình song song có thể được thể hiện dưới một phần cứng bất kì.\\
\indent Dưới đây là hai mô hinh lập trình song song phổ biến.

\subsection{Lập trình chia sẻ bộ nhớ}
Trong mô hình lập trình chia sẻ bộ nhớ, các tác vụ chia sẻ một không gian địa chỉ chung nơi các tác vụ đọc và ghi dữ liệu.\\
\indent Các cơ chế khác nhau như locks/semaphores có thể được dùng để điều khiển việc truy cập tới bộ nhớ chia sẻ.\\
\indent	Một ưu điểm của mô hình này theo quan điểm của người lập trình đó là không có quyền sở hữu dữ liệu riêng nên không cần phải đặc tả việc truyền thông dữ liệu hiển giữa các tác vụ. Việc phát triển chương trình có thể được đơn giản hóa.\\
\indent Nhược điểm quan trọng của mô hình là các ngôn ngữ của việc thực hiện, nó trở nên khó hiểu và khó quản lý vùng dữ liệu hơn.\\

\subsubsection{Lập trình chia sẻ bộ nhớ dựa vào tiến trình}
\begin{itemize}
\item Tiến trình (processes) là một bản thể của chương trình đang thực thi. Yêu cầu của xử lý song song là khả năng tạo ra một số tiến trình cần thiết cho bài toán và khả năng hủy bỏ tiến trình khi phần việc xử lý song song kết thúc để giải phóng các tài nguyên mà tiến trình đã chiếm giữ và không cản trở hoạt động của những tiến trình khác.
\item Các hệ điều hành như Linux, Unix hay Windows đều phải điều phối sự hoạt động đồng bộ của các tiến trình. Khi muốn sử dụng bộ nhớ chung, ta cần phải xin cấp phát bộ nhớ và sau đó khi sử dụng xong phải giải phóng chúng. 
\item Khi có một tiến trình truy cập vào một bộ nhớ với mục đích cập nhật thì nó phải được đảm bảo rằng không một tiến trình dữ liệu nào khác đọc dữ liệu ở vùng nhớ đó cho tới khi việc cập nhật đó kết thúc.\\
\end{itemize}

\subsubsection{Lập trình chia sẻ bộ nhớ dựa vào luồng}
\begin{itemize}
\item Khái niệm luồng
\begin{itemize}
\item Luồng (\textit{thread}) cũng giống như các tiến trình là kĩ thuật cho phép một chương trình có thể thực hiện nhiều công việc tại một thời điểm, thực hiện công việc tại một khoảng thời gian cho trước. Các luồng tồn tại bên trong các tiến trình.
\item Các luồng của một tiến trình có thể chia sẻ với nhau về không gian địa chỉ chương trình, các đoạn dữ liệu và môi trường xử lý, đồng thời cũng có những vùng dữ liệu riêng để thao tác.
\item Công việc của một luồng có thể được miêu tả như là một chương trình con của một chương trình chính. Một luồng bất kì có thể thực thi một chương trình con bất kì cùng lúc với các luồng khác.
\item Các luồng giao tiếp với các luồng khác qua bộ nhớ toàn cục (global memory). Việc này yêu cầu xây dựng việc đồng bộ để đảm bảo rằng chỉ có một luồng cập nhật một địa chỉ chung tại một thời điểm. Việc đồng bộ các luồng thực hiện hiệu quả hơn đối với các tiến trình vì đồng bộ luồng chủ yếu tập trung vào sự truy cập các biến chung của chương trình.
\end{itemize}
\item Các thể hiện của luồng
\indent Có nhiều hệ điều hành hỗ trợ đa luồng như:  SUN Solaris, Windows NT v.v. những nỗ lực tiêu chuẩn hóa không giống nhau đã đưa tới hai thể hiện rất khác nhau của luồng đó là: POSIX Threads và OpenMP.
\subitem \textbf{POSIX Threads}: Thường được gọi là Pthreads
\begin{itemize}
\item Thư viện cơ sở yêu cầu sự mã hóa song song.
\item Được chỉ rõ bởi tiêu chuẩn IEEE POSIX 1003.1c (1995)
\item Chỉ sử dụng ngôn ngữ C
\item Hầu hết các nhà cung cấp phần cứng hiện này đều đề xuất Pthreads ngoài các thể hiện luồng riêng của họ.
\item Tính song song rất rõ ràng, yêu cầu người lập trình chú ý tới chi tiết
\end{itemize}
\subitem \textbf{OpenMP}
\begin{itemize}
\item Cơ sở chỉ thị biên dịch có thể sử dụng mã tuần tự.
\item Được định nghĩa và chứng thực bởi một nhóm các nhà cung cấp phần cứng và phần mềm chủ yếu. OpenMP Fortran API được phát hành ngày 28 tháng 10 năm 1997. C/C++ được phát hành muộn hơn vào năm 1998.
\item Các nền lập trình bao gồm Unix và Windows NT.
\item Có sẵn trong các thể hiện của C/C++ và Fortran.
\item Có thể được sử dụng để cung cấp cho các bài toán có tính song song gia tăng dễ dàng và đơn giản.
\end{itemize}
\end{itemize}

\subsection{Mô hình truyền thông điệp}
Giống như mô hình chia sẻ bộ nhớ, các đơn vị xử lý song trong mô hình truyền thông điệp là các tiến trình. Trong mô hình truyền thông điệp:
\begin{itemize}
\item Các tiến trình có thể thực hiện trên những bộ xử lý khác nhau và không được truy cập vào không gian bộ nhớ chia sẻ.
\item Việc truyền thông giữa các tiến trình thông qua việc gửi và nhận thông điệp.
\item Việc đồng bộ hóa các tiến trình của một chương trình song song được thực hiện theo cơ chế truyền thông điệp. Khi một tiến trình muốn gửi một thông điệp thì nó phải chờ cho đến khi tiến trình nhận sẵn sàng nhận thông điệp đó và ngược lại, cũng tương tự.
\end{itemize}
\subsubsection{Các thể hiện của mô hình truyền thông điệp}
\begin{itemize}
\item Các thể hiện của mô hình truyền thông điệp thường chứa một thư viện các hàm con được nhúng trong mã nguồn. Người lập trình có nhiệm vụ xác định tất cả các khả năng song song.
\item Trong những năm 1980 có nhiều thư viện truyền thông điệp khác nhau. Điều này dẫn đến khó khăn cho những người lập trình khi muốn phát triển một ứng dụng hiện có.
\item Năm 1992, một thư viện chuẩn của mô hình truyền thông điệp đã được thiết lập, đó là chuẩn MPI(\textit{Message Passing Interface}).
\end{itemize}
\indent Ngoài ra còn một số mô hình lập trình song song thường dùng khác như song song dữ liệu, Hybrid, SPMD, MPMD...

\section{Thuật toán song song}
\subsection{Nguyên lý thiết kế thuật toán song song}
Phát triển thuật toán là một phần cơ bản của việc giải quyết bài toán sử dụng máy tính. Một thuật toán tuần tự về bản chất là một cách làm hay một số tuần tự các bước để giải quyết bài toán đưa ra bằng một máy tính tuần tự. Một cách tương tự, một thuật toán song song là một cách làm chỉ cho chúng ta làm thế nào để giải quyết bài toán đưa ra bằng các máy tính song song.\\
\indent Tuy nhiên, việc đặc tả một thuật toán song song liên quan tới nhiều hơn là việc đặc tả các bước. Ít nhất thì một thuật toán song song có thêm kích thước tương tranh và người thiết kế thuật toán phải chỉ rõ các bước nào có thể thực hiện một cách đồng thời. Đây cũng chính là nguyên nhân để có thể đạt được bất cứ lợi ích nào từ việc sử dụng các máy tính song song.\\
\indent Trong thực tế, việc xây dựng một thuật toán song song có thể gồm một số hoặc tất cả các bước sau:
\begin{itemize}
\item Xác định các phần công việc có thể thực hiện đồng thời.
\item Gán các công việc có thể thực hiện đồng thời vào nhiều tiến trình chạy song song.
\item Phân tán dữ liệu đầu vào, đầu ra, và trung gian.
\item Quản lý việc truy cập tơi dữ liệu chia sẻ.
\item Đồng bộ các bộ xử lý ở các giai đoạn khác nhau của việc thực thi chương trình song song.
\end{itemize}
\indent Có năm nguyên lý chính trong thiết kế thuật toán song song:
\begin{description}
\item[Các nguyên lý lập lịch] Giảm tối thiểu các bộ xử lý sử dụng trong thuật toán song song sao cho thời gian tính toán không tăng(Xét theo khía cạnh độ phức tạp).
\item[Nguyên lý hình ống] Nguyên lý áp dụng khi bài toán xuất hiện một dãy các thao tác $\{T_0, T_1,\ldots, T_{n-1}\}$, trong đó $T_{i+1}$ được thực hiện sau khi $T_i$ kết thúc.
\item[Nguyên lý chia để trị] Chia bài toán thành những phần nhỏ hơn có dạng giống với bài toán ban đầu và giải quyết chúng một cách song song.
\item[Nguyên lý đồ thị phụ thuộc dữ liệu] Phân tích mối quan hệ dữ liệu trong tính toán để xây dựng đồ thị phụ thuộc dữ liệu và dựa vào đồ thị phụ thuộc để xây dựng thuật toán song song.
\item[Nguyên lý điều kiện ganh đua] Nếu hai tiến trình cùng muốn truy cập vào cùng một mục dữ liệu chia sẻ thì chúng có thể cản trở lẫn nhau. Hai tiến trình ở trong trạng thái ganh đua nếu đầu ra của việc tính toán phụ thuộc hoàn toàn vào việc tiến trình nào truy cập dữ liệu chia sẻ trước nhất.
\end{description}
Trên những kiến trúc máy tính khác nhau thì hiệu quả của thuật toán có thể rất khác nhau. Việc thiết kế thuật toán song song phải được dựa trên những kiến thức về kiến trúc máy tính, ngôn ngữ lập trình song song và các phương pháp tính toán.\\
\paragraph{Một số khái niệm}
\begin{description}
\item[Tác vụ (\textit{Task})] là đơn vị do người dùng định nghĩa, trong đó việc tính toán chính được chia nhỏ bằng các kĩ thuật phân chia. Các tác vụ có thể được phân chia với cùng kích cỡ hoặc không cùng kích cỡ, có thể được sinh tĩnh, tức là các tác vụ được xác định trước khi thực hiện thuật toán, và sinh động ngược lại với sinh tĩnh, các tác vụ không được biết trước. Một tác vụ không thể chia nhỏ được nữa gọi là tác vụ nguyên tử.
\item[Tiến trình(\textit{process})] là các tác nhân tính toán logic thực hiện các tác vụ.
\item[Thực hiện tuần tự] là việc thực hiện chương trình một cách tuần tự trên máy một bộ xử lý, một câu lệnh tại một thời điểm.
\item[Thực hiện song song] là việc thực hiện chương trình bằng nhiều hơn một tác vụ, mỗi tác vụ có thể được thực thi với cùng hoặc không cùng một câu lệnh tại cùng một thời điểm.
\end{description}
\paragraph{Phương pháp luận để thiết kế thuật toán song song} gồm bốn giai đoạn khác nhau như sau:\begin{enumerate}
\begin{figure}[!ht]
\centering
\includegraphics[scale=0.6]{ppthietke}
\caption{\textit{Phương pháp luận thiết kế thuật toán song song}}\label{fig:}
\end{figure}
\item Sự chia nhỏ bài toán (\textit{partitioning}): Sự tính toán và dữ liệu được chia thành các phần nhỏ. Ta không quan tâm tới có bao nhiêu bộ xử lý mà chỉ tập trung vào khả năng thực hiện song song của các phần nhỏ.
\item Thiết lập kênh truyền(\textit{communication}): Thiết lập kênh truyền đòi hỏi tọa độ của các tác vụ thực hiện, cấu trúc kênh truyền và cấu trúc truyền thông điệp(đặc tả các thông điệp được gửi). Tối ưu hóa việc thực hiện bằng cách phân bố truyền thông trên nhiều tác vụ và thực hiện một cách đồng thời.
\item Nhóm gom các tác vụ(\textit{agglomeration}): Ta đánh giá cấu trúc tác vụ và sự truyền thông ở các bước trên quan tâm tới việc thể hiện. Sau đó, xử lý độ hạt tác vụ và tối ưu hóa kênh truyền thông.
\item Gán vào hệ thống(\textit{mapping}): Mỗi tác vụ được gán vào một bộ xử lý sao cho sử dụng hiệu quả các bộ xử lý và giảm truyền thông tới mức tối thiểu.
\end{enumerate}
\subsubsection{Các cách tiếp cận trong thiết kế}
Có ba cách tiếp cận để thiết kế thuật toán song song:
\begin{enumerate}
\item Thực hiện song song hóa những thuật toán tuần tự, biến đổi những cấu trúc tuần tự để tận dụng được những khả năng song song tự nhiên của tất cả các thành phần trong hệ thống xử lý.
\item Thiết kế những thuật toán song song mới phù hợp với kiến trúc song song.
\item Thiết kế những thuật toán song song mới từ những thuật toán song song đã có sao cho phù hợp với cấu hình tôpô và môi trường song song trong thực tế.
\end{enumerate}
Trong các cách tiếp cận trên thì cách tiếp cận thông dụng là song song hóa các thuật toán tuần tự hoặc là chuyển một dạng song song về một dạng song song phù hợp hơn sao cho vẫn bảo toàn được tính tương đương trong tính toán.\\
Trong thiết kế thuật toán song song, chúng ta cần trả lời được hai câu hỏi sau:
\begin{itemize}
\item[$\circ$] Kiến trúc nào là phù hợp nhất với bài toán chúng ta đang giải quyết?
\item[$\circ$] Bài toán có thể đạt được hiệu quả gì trên một kiến trúc song song cho trước? 
\end{itemize}


\subsection{Đánh giá các thuật toán song song}
Để đánh giá được độ phức tạp của thuật toán song song chúng ta cần đánh giá số các bước tính và đánh giá thời gian truyền thông giữa các tiến trình.\\
\subsubsection{Thời gian thực hiện song song}
Thời gian thực hiện song song, kí hiệu là $t_p$ gồm có hai phần thời gian thực hiện các phép tính, kí hiệu là $t_{comp}$ và thời gian thực hiện truyền thông, kí hiệu là $t_{comm}$.\\
Ta có, \[t_p=t_{comp}+t_{comm}\]
Thời gian tính toán $t_{comp}$ được xác định giống như thuật toán tuần tự. Khi có nhiều tiến trình thực hiện đồng thời thì chỉ cần tính thời gian thực hiện của tiến trình phức tạp nhất (thực hiện lâu nhất). Trong việc phân tích thời gian tính toán, chúng ta luôn giả thiết rằng các bộ xử lý là giống nhau và thực hiện với một tốc độ giống nhau.\\
Thời gian truyền thông $t_{comm}$ phụ thuộc vào vào kích cỡ các thông điệp, cấu trúc kết nối mạng đường truyền và cách thức truyền tải thông điệp,v.v. Công thức ước lượng thời gian truyền thông được tính như sau: \[t_{comm}=t_{startup}+n*t_{data}\]
Trong đó,
\begin{itemize}
\item [$\circ$ ] $t_{startup}$ là thời gian cần thiết để gửi thông điệp không phải là dữ liệu. Nó bao gồm thời gian để đóng gói thông điệp ở nơi gửi và thời gian mở gói thông điệp ở nơi nhận. Để đơn giản chúng ta giả thiết thời gian này là hằng số.
\item [$\circ$ ] $t_{data}$ là thời gian cần thiết chuyển một từ dữ liệu từ nơi gửi tới nơi nhận, được giả thiết là hằng số và $n$ là số từ dữ liệu được trao đổi trong hệ thống. 
\end{itemize}
\subsubsection{Độ phức tạp thời gian của thuật toán song song}
Độ phức tạp thời gian của việc thực hiện song song, $t_p$, là tổng độ phức tạp của các phép toán và sự truyền thông.\\
\indent \textbf{Ví dụ}\\
\indent Giả sử cần thực hiện cộng $n$ số trên hai máy tính, trong đó mỗi máy cộng $n/2$ số với nhau và tất cả các số đó được lưu ở máy thứ nhất. Máy thứ hai phải gửi kết quả của mình cho máy thứ nhất để cộng hai tổng thành phần với nhau. Bài toán có các bước sau:
\begin{enumerate}
\item Máy một gửi $n/2$ số cho máy hai.
\item Cả hai máy thực hiện cộng $n/2$ số một cách đồng thời.
\item Máy hai gửi kết quả tính được cho máy một.
\item Máy một cộng hai tổng thành phần để đưa ra kết quả cuối cùng.
\end{enumerate}

\indent \textit{Thời gian tính toán} (ở bước 2 và 4):\[t_{comp}=n/2+1\]
\indent \textit{Thời gian truyền thông} (ở bước 1 và 3):\[t_{comm}=(t_{startup}+n/2t_{data})+(t_{startup}+1t_{data})=2t_{startup}+(n/2+1)t_{data}\]
\indent Độ phức tạp tính toán là O($n$). Độ phức tạp truyền thông là O($n$). Vậy độ phức tạp thời gian của thuật toán nói trên là O($n$)

\subsubsection{Tỉ số giữa thời gian tính toán và truyền thông}
Thường thì thời gian truyền thông rất đắt. Nếu sự tính toán và truyền thông có cùng độ phức tạp thì việc thực hiện khi tăng $n$ sẽ không mang lại hiệu quả tốt hơn. Do vậy độ phức tạp thời gian của việc tính toán nên lớn hơn độ phức tạp thời gian truyền thông, khi đó việc tăng $n$ sẽ cải thiện được rất nhiều việc thực hiện.\\
\indent Giả sử, một bài toán có độ phức tạp thời gian truyền thông là O($n$), độ phức tạp thời gian tính toán là O($n^2$). Việc tăng $n$ cuối cùng sẽ có một giá trị $n$ mà tại đó thời gian tính toán lớn hơn rất nhiều so với thời gian thực thi.

\subsubsection{Thuật toán có chi phí tốt}
Một thuật toán có chi phí tốt nhất nếu chi phí để giải quyết bài toán tỉ lệ với thời gian thực hiện trên hệ thống một bộ xử lý đơn (sử dụng thuật toán tuần tự tốt nhất). Tức là,\\
 \[Cost =t_p\times n=k\times t_s\] trong đó, $Cost$ là chi phí thực hiện, $k$ là hằng số.
Một thuật toán song song là thuật toán có chi phí tốt nhất nếu\\ (độ phức tạp thời gian song song)$\times$(số bộ xử lý)$=$(độ phức tạp thời gian tuần tự)\\
\indent \textbf{Ví dụ}\\
\indent Giả sử một thuật toán tuần tự tốt nhất để giải một bài toán có độ phức tạp thời gian là O($nlogn$). Thì một thuật toán song song để giải bài toán trên sử dụng $n$ bộ xử lý có độ phức tap thời gian là O($logn$) là tốt nhất, trái lại nếu thuật toán đó sử dụng $n^2$ bộ xử lý và có độ phức tạp thời gian là O($1$) lại là thuật toán không có chi phí tốt nhất.
Ngoài ra để đánh giá một thuật toán song song ta phải xét đến hệ số gia tốc của thuật toán. Hệ số gia tốc của thuật toán song song sử dụng $p$ bộ xử lý được xác định như sau: 
\[S_p=T_s/T_p\]
trong đó, \begin{itemize}
\item [$+$] $T_s$ là thời gian thực hiện tính toán trên một bộ xử lý.
\item [$+$] $T_p$ là thời gian thực hiện trên $p$ bộ xử lý. 
\end{itemize}
\section{Lập trình song song với MPI}
Lập trình song song cũng giống với lập trình tuần tự, có nhiều ngôn ngữ và công cụ lập trình song song khác nhau. Lập trình theo mô hình truyền thông điệp trong hệ thống máy tính có thể thực hiện theo 3 cách:
\begin{enumerate}
\item Sử dụng ngôn ngữ lập trình song song đặc biệt, ví dụ Occam được thiết kế để sử dụng với các Transputer (Inmos 1986).
\item Sử dụng ngôn ngữ lập trình bậc cao (tuần tự) truyền thống được mở rộng bằng cách bổ sung thêm các từ khóa và mở rộng một cú pháp để xử lý việc trao đổi thông điệp, gồm có CC+ (mở rộng từ C++)và Fortran M (mở rộng từ Fortran).
\item Sử dụng những ngôn ngữ lập trình bậc cao như là ngôn ngữ C và cung cấp một thư viện các thủ tục bên ngoài để thực hiện truyền thông điệp. 
\end{enumerate}
Lập trình song song với MPI là lập trình theo mô hình truyền thông điệp trong hệ thống máy tính sử dụng cách tiếp cận thứ ba.
\subsection{Giới thiệu về MPI(\textit{Message Passing Interface})}
Với mục đích xây dựng một thư viện truyền thông điệp chuẩn, MPI đã ra đời và hoàn thành lần đầu tiên vào tháng 6 năm 1994, MPI đã được chấp nhận và sử dụng rộng rãi trên các hệ thống phân cấp (Scalable Parallel Computers - SPCs) và các hệ thống máy trạm (Networks Of Workstations - NOWs).\\
\indent MPI không phải là một ngôn ngữ lập trình mới mà là một thư viện gồm các định nghĩa và các hàm được gọi vào từ chương trình C hoặc Fortran.\\
\paragraph{Ưu điểm}
\begin{itemize}
\item Chuẩn MPI được thiết kế để phục vụ tất cả các đối tượng có nhu cầu lập trình song song sử dụng mô hình truyền thông điệp trên Fortran 77 hoặc C. Để đạt được mục đích ấy, chuẩn MPI cung cấp một giao diện đơn giản, dễ sử dụng cho đa số người dùng song vẫn đảm bảo hiệu năng cao trên các máy tính tiên tiến.
\item MPI phát triển một cách rộng rãi các tiêu chuẩn để viết các chương trình có sử dụng truyền thông điệp. Những tiêu chuẩn này phải đảm bảo yêu cầu cần thực hành hiệu quả và linh hoạt, bao gồm:
\begin{itemize}
\item Thiết kế giao diện lập trình ứng dụng (không phải là thư viện bắt buộc để dịch và thực thi chương trình)
\item Đảm bảo truyền thông hiệu quả, tránh sao chép bộ nhớ, đồng thời cho phép gối lên nhau giữa tính toán và truyền thông.
\item Cho phép thực thi trên một môi trường hỗn hợp.
\item Cho phép liên kết với các tiện ích của C và Fortran 77.
\item Cung cấp một giao diện truyền thông đáng tin cậy: người sử dụng không phải đối mặt với các lỗi truyền thông, các lỗi này sẽ được xử lý bởi các hệ thống con bên dưới.
\item Không khác quá nhiều so với các giao diện đã có như PVM, NX, Express, p4,..., song lại cung cấp các mở rộng linh hoạt hơn.
\item Có ngôn ngữ riêng.
\item Giao diện đảm bảo an toàn luồng.
\end{itemize}
\end{itemize}
\indent Với những ưu điểm của mình chuẩn MPI đang trở thành lựa chọn ưu tiên của các nhà lập trình song song trên mô hình truyền thông điệp.
\paragraph{Hạn chế} Chuẩn MPI không cung cấp:
\begin{itemize}
\item Những thao tác phân tán bộ nhớ rõ ràng.
\item Những thao tác đòi hỏi nhiều hệ điều hành hỗ trợ hơn chuẩn hiện thời, ví dụ thao tác nhận tự ngắt, thực hiện từ xa hoặc những thông điệp hoạt động.
\item Lập trình các công cụ cấu trúc.
\item Các công cụ gỡ lỗi.
\item Hỗ trợ quản lý tác vụ.
\item Hỗ trợ luồng một cách rõ ràng.
\item Các hàm vào/ra (I/O)
\end{itemize}
\indent Những đặc tính trên luôn được xem xét như những mở rộng của chuẩn trong những thực thi xác định cụ thể và các phiên bản sau của MPI cố gắng tích hợp thêm nhiều tính năng mới.\\
\indent Hiện nay, MPI đã có phiên bản 2.0 với các ưu điểm nổi bật:
\begin{itemize}
\item Cho phép sinh tiến trình động (số lượng tiến trình có thể thay đổi trong suốt quá trình thực thi chương trình).
\item Cho phép truyền thông một phía (tức là việc truyền thông được phát sinh và thực hiện ngay trong một bộ xử lý).
\item Mở rộng thêm các thao tác truyền thông tập hợp (cho phép truyền thông giữa các nhóm tiến trình với nhau, mỗi nhóm tạo thành một bộ truyền thông).
\item Mở rộng giao diện, hỗ trợ I/O, hỗ trợ C++ và Fortran 90,...
\end{itemize}

\subsection{Các hàm cơ bản trong chuẩn MPI}
Trong mô hình lập trình MPI, việc tính toán bao gồm một hoặc nhiều tiến trình truyền thông với nhau bằng cách goi thư viện hàm để gửi và nhận thông điệp từ những tiến trình khác. Trong hầu hết các thể hiện MPI, một tập hợp cố định các tiến trình được tạo ra khi khởi tạo chương trình, và một tiến trình được tạo bởi một bộ xử lý.\\
\indent Hai phương thức chính cần thiết cho mô hình lập trình truyền thông điệp dạng này là:
\begin{itemize}
\item Phương thức tạo các tiến trình riêng biệt để thực thi trên các máy tính khác nhau.
\item Phương thức gửi và nhận thông điệp. 
\end{itemize}
\subsubsection{Việc tạo lập tiến trình}
Phiên bản 1 của MPI chỉ hỗ trợ việc tạo lập tiến trình tĩnh. Tức là, tất cả các tiến trình được xác định trước khi thực hiện và bắt đầu cùng với nhau. Phiên bản 2 của MPI đã hỗ trợ việc tạo lập tiến trình động nhưng nó thường không được sử dụng vì tổng phí của việc tạo lập tiến trình động.\\
\indent Trong mô hình lập trình MPI thường sử dụng mô hình tính toán SPMD. Trong hệ thống thường có một tiến trình chủ (\textit{master}) điều khiển các tiến trình khác được gọi là tiến trình tớ (\textit{slave})\\
\indent Các tiến trình được đánh số từ $0$ đến $(p-1)$ dùng để định danh các tiến trình, các số này gọi là hạng của tiến trình, $p$ là số tiến trình được sử dụng.\\
\indent Số lượng các hàm trong MPI rất nhiều, tuy nhiên chúng ta có thể xây dựng chương trình dựa trên các hàm cơ bản sau:
\subsubsection{Các hàm quản lý môi trường}
\begin{itemize}
\item \textbf{Hàm khởi tạo MPI}\\
\hspace*{0.75in} \textsf{int MPI$\_$Init(Int${}^{*}$ argc, char${}^{*}$ argv)}\\
Ý nghĩa: hàm này dùng để khởi tạo môi trường truyền thông điệp MPI. Nó phải được gọi trước bất cứ hàm MPI nào. Tham số của nó là con trỏ trỏ tới các tham số của hàm \textit{main( )}.
\item \textbf{Hàm kết thúc MPI}\\
\hspace*{0.75in} \textsf{int MPI$\_$Finalize(void)}\\
Ý nghĩa: đây là hàm đóng môi trường MPI. Sau lời gọi hàm này không còn lời gọi hàm MPI nào có hiệu lực.
\end{itemize}
\subsubsection{Các hàm truyền thông điệp điểm-điểm}
\begin{itemize}
\item \textbf{Hàm gửi thông điệp}\\
\hspace*{0.75in} \textsf{int MPI$\_$Send(void ${}^{*}$buf, int count, MPI$\_$Datatype datatype, int dest, int tag, MPI$\_$Comm comm)}\\
Trong đó,
\begin{itemize}
\item \textsf{buf}: địa chỉ bắt đầu của bộ đệm gửi
\item \textsf{count}: số các thành phần trong bộ đệm
\item \textsf{datatype}: kiểu dữ liệu của mỗi thành phần trong bộ đệm
\item \textsf{dest}: hạng của tiến trình nhận
\item \textsf{tag}: nhãn của thông điệp được gửi
\item \textsf{comm}: bộ truyền thông điệp, đó là tập hợp của các tiến trình mà các tiến trình có thể gửi và nhận thông điệp.\\
\indent Ý nghĩa: hàm này dùng để gửi thông điệp có nhãn là \textsf{tag} và chứa dữ liệu ở bộ đệm \textsf{buf} với số lượng \textsf{count} phần tử kiểu \textsf{datatype} tới tiến trình có số hiệu \textsf{dest}.\\
\indent Một thông điệp được gửi tới một tiến trình cụ thể và được đánh dấu bởi một nhãn (giá trị là số nguyên) do người sử dụng xác định. Các nhãn được dùng để phân biệt những kiểu thông điệp khác nhau mà một tiến trình gửi (hoặc nhận). Nhãn thông điệp có thể dùng MPI$\_$ANY$\_$TAG khi thông điệp được gửi (hoặc nhận) có thể ở bất kỳ định dạng nào. Tương tự, ta có thể dùng MPI$\_$ANY$\_$SOURCE để nhận thông điệp từ bất kỳ tiến trình nào.
\end{itemize}
\item \textbf{Hàm nhận thông điệp}\\
\hspace*{0.75in} \textsf{int MPI$\_$Recv(void ${}^{*}$buf, int count, MPI$\_$Datatype datatype, int source, int tag, MPI$\_$Status status)}\\
Ý nghĩa: hàm này dùng để nhận thông điệp từ tiến trình có số hiệu \textsf{source} với nhãn là \textsf{tag} dữ liệu và lưu vào bộ đệm \textsf{buf} với số phần tử là \textsf{count} có kiểu dữ liệu \textsf{datatype} và trả lại thông tin về dữ liệu thật sự nhận được trong biến trạng thái \textsf{status}.\\
\indent \textsf{status} là kiểu dữ liệu có cấu trúc, chứa ít nhất 3 thành phần là số hiệu tiến trình gửi (\textsf{source}), nhãn (\textsf{tag}) và mã lỗi. Nhãn thông báo nhận được là \textsf{status.MPI$\_$TAG} và hạng của tiến trình gửi là \textsf{status.MPI$\_$SOURCE}. Khi số lượng phần tử nhận được có thể nhỏ hơn \textsf{count}, hàm sau đây có chức năng trả lại số lượng các phần tử nhận được \textsf{MPI$\_$Get$\_$count($\&$status, datatype, $\&$nelements)}. 
\end{itemize}

\subsubsection{Các hàm truyền thông tập thể}
\begin{figure}[!ht]
\centering
\includegraphics[scale=0.75]{hamtruyenthong}
\caption{\textit{Hàm giao tiếp tập thể của MPI}}\label{fig:}
\end{figure}
\begin{itemize}
\item \textbf{Hàm quảng bá thông điệp (loan tin)}\\
\hspace*{0.75in} \textsf{int MPI$\_$Bcast(void ${}^{*}$buf, int count, MPI$\_$Datatype datatype, int root, MPI$\_$Comm comm)}\\
\indent Trong đó, các tham số \textsf{buf, count, datatype, comm} tương tự như trong hàm \textsf{MPI$\_$Send}. Tham biến \textsf{root} chính là hạng của tiến trình tiến hành loan tin.\\
Ý nghĩa: hàm này dùng để gửi một nội dung \textsf{buf} từ tiến trình có hạng \textsf{root} tới tất cả các tiến trình trong bộ truyền thông.\\
\item \textbf{Hàm tổng hợp dữ liệu}\\
\hspace*{0.75in}\textsf{int MPI$\_$Gather(void ${}^{*}$sendbuf, int sendcount, MPI$\_$Datatype sendtype, void ${}^{*}$recvbuf, int recvcount, MPI$\_$Datatype recvtype, int root, MPI$\_$comm comm)}\\
Ý nghĩa: tiến trình có số hiệu \textsf{root} thu thập dữ liệu trong bộ đệm \textsf{sendbuf} từ tất cả các tiến trình trong bộ truyền thông và lưu vào trong bộ đệm \textsf{recvbuf} theo thứ tự hạng của các tiến trình.\\
\item \textbf{Hàm phân phối dữ liệu}\\
\hspace*{0.75in} \textsf{MPI$\_$Scatter(void ${}^{*}$sendbuf, int sendcount, MPI$\_$Datatype sendtype, void ${}^{*}$recvbuf, int recvcount, MPI$\_$Datatype recvtype, MPI$\_$comm comm)}\\
Ý nghĩa: tiến trình có số hiệu \textsf{root} phân phối dữ liệu từ \textsf{sendbuf} tới tất cả các tiến trình trong bộ truyền thông theo thứ tự hạng của tiến trình.\\
\item \textbf{Hàm tổng hợp toàn bộ dữ liệu}\\
\hspace*{0.75in} \textsf{MPI$\_$allGather(void ${}^{*}$sendbuf, int sendcount, MPI$\_$Datatype sendtype, void ${}^{*}$recvbuf, int recvcount, MPI$\_$Datatype recvtype, MPI$\_$comm comm)}\\
Ý nghĩa: các tiến trình thu thập dữ liệu trong bộ đệm \textsf{sendbuf} từ tất cả các tiến trình trong bộ truyền thông và lưu vào trong bộ đệm \textsf{recvbuf} theo thứ tự hạng của tiến trình.
\end{itemize}
\subsubsection{Các hàm quản lý nhóm}
\begin{itemize}
\item \textbf{Hàm lấy hạng của tiến trình}\\
\hspace*{0.75in}\textsf{int MPI$\_$Comm$\_$rank(MPI$\_$Comm comm, int ${}^{*}$rank)}\\
Ý nghĩa: hàm này trả lại giá trị hạng của tiến trình trong bộ truyền thông đang gọi hàm.
\item \textbf{Hàm lấy số tiến trình}\\
\hspace*{0.75in}\textsf{int MPI$\_$Comm$\_$size(MPI$\_$Comm com, int ${}^{*}$size)}\\
Ý nghĩa: hàm này trả lại giá trị là số lượng các tiến trình trong bộ truyền thông \textsf{com}.
\end{itemize}	
\subsubsection{Ví dụ về một chương trình MPI đơn giản}
Viết chương trình in ra tên máy và chỉ số rank của process MPI đang thực thi tên máy.\\
$\#$include$<stdio.h>$\\
$\#$include$<mpi.h>$\\
\hspace*{1cm}int main(int argc, char${}^{*}$ argv[])\\
\hspace*{1cm}\{\\
\hspace*{2.5cm} int length;\\
\hspace*{2.5cm} char name[BUFSIZ];\\
\hspace*{2.5cm} MPI$\_$Init($\&$argc, $\&$argv);\\
\hspace*{2.5cm} MPI$\_$Get$\_$processor$\_$name(name, $\&$length);\\
\hspace*{2.5cm} printf("\%s Hello world $\backslash$n", name);\\
\hspace*{2.5cm} MPI$\_$Finalize();\\
\hspace*{1cm} \}


